In recent years, adversaries have been growing their abilities with the progress in computers, and the size of cryptosystems for making cryptanalysis difficult is increasing year after year. The increase in the size of security parameters of cryptosystems is an issue when public key cryptography is employed in small devices that do not have sufficient memory capacities and communication bands.
Accordingly, compressed encryption technologies for compressing the size of public keys and the size of encrypted data in public key cryptography have been proposed (see, for example, K. Rubin and A. Silverberg, “Torus-Based Cryptography”, CRYPTO 2003, Springer LNCS 2729, pp. 349-365, 2003). The compressed encryption technologies are based on the fact that elements of a set can be represented by a small number of bits by using a subset called an algebraic torus among sets of elements used in public key cryptography. In addition, technologies using additional input for converting elements of a set into a representation with a small number of bits are known as technologies for increasing the compression ratio (see, for example, M. van Dijk and D. Woodruff, “Asymptotically Optimal Communication for Torus-Based Cryptography”, CRYPTO 2004, Springer LNCS 3152, pp. 157-178, 2004).
In addition, in recent years, security against unauthorized attacks such as side channel attacks attempting code-breaking of secret information through power analysis or electromagnetic analysis or the like may be lowered in public key cryptosystems (see, for example, J. S. Coron, “Resistance Against Differential Power Analysis for Elliptic Curve Cryptosystems”, CHES1999, Springer LNCS1717, pp. 292-302, 1999). In Furuta et al., “Projective Representation Randomization against DPA in Torus-Based Cryptosystems”, Proceedings of the Institute of Electronics, Information and Communication Engineers General Conference A-7-6, 2009, measures are taken against side channel attacks through differential power analysis (DPA) by randomizing projective representations of ciphers using algebraic tori.
However, the computational cost of multiplication performed in the course of randomly selecting elements of an algebraic torus is large in the measures using algebraic tori against side channel attacks as in “Projective Representation Randomization against DPA in Torus-Based Cryptosystems” described above.